/*
 * @lc app=leetcode.cn id=839 lang=javascript
 *
 * [839] 相似字符串组
 */

// @lc code=start
/**
 * @param {string[]} strs
 * @return {number}
 */
var numSimilarGroups = function (strs) {
  const size = strs.length;
  const uf = new UnionFind(size);
  for (let i = 0; i < size; i++) {
    for (let j = i + 1; j < size; j++) {
      if (uf.conncted(i, j)) {
        continue;
      }
      uf.union(i, j, strs);
    }
  }
  return uf.count;
};

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x) {
    return x !== this.parent[x]
      ? (this.parent[x] = this.find(this.parent[x]))
      : x;
  }
  union(x, y, strs) {
    let ux = this.find(x);
    let uy = this.find(y);
    let num = 0;
    // 相似字符串连通
    for (let i = 0; i < strs[x].length; i++) {
      if (strs[x][i] !== strs[y][i]) {
        num++;
      }
      if (num > 2) {
        return false;
      }
    }

    if (this.size[ux] > this.size[uy]) {
      [ux, uy] = [uy, ux];
    }
    this.parent[ux] = uy;
    this.size[uy] += this.size[ux];
    this.count--;
    return true;
  }
  conncted(x, y) {
    let ux = this.find(x);
    let uy = this.find(y);
    return this.parent[ux] === this.parent[uy];
  }
}
// @lc code=end
